//
// Created by 高森森 on 2022/2/9.
//

#ifndef LEETCODE_SOLUTION25_H
#define LEETCODE_SOLUTION25_H
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Solution25 {
public:
    const int INF=10e7;
    vector<vector<vector<int>>>graph;
    int dfs(int src,int dst,int k,vector<vector<int>>&memory){
        if(k<0){
            return INF;
        }
        if(src==dst){
            return 0;
        }
        if(memory[src][k]!=0)
            return memory[src][k];

        int mini=INF;
        for(auto neigh:graph[src]){
            int temp=dfs(neigh[0],dst,k-1,memory)+neigh[1];
              mini= min(temp,mini);
            }
        memory[src][k]=mini;
        return mini;
        }
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        graph=vector<vector<vector<int>>>(n);
        for(auto flight:flights){
            graph[flight[0]].push_back(vector<int>{flight[1],flight[2]});
        }
        vector<vector<int>>memory(n,vector<int>(k+2));
        return dfs(src,dst,k+1,memory)==INT_MAX?-1:dfs(src,dst,k+1,memory);
    }
    int dp(int n,vector<vector<int>>& flights, int src, int dst,int K){
        vector<vector<int>>dp(n,vector<int>(K+2,INF));
        dp[dst][0]=0;
        for(int k=1;k<=K+1;k++)
        {
            for(auto flight:flights){
                dp[flight[0]][k]=min(dp[flight[0]][k],dp[flight[1]][k-1]+flight[2]);
            }
        }
        int ans=INF;
        for(int i=1;i<=K+1;i++){
            ans=min(ans,dp[src][i]);
        }
        return ans==INF?-1:ans;
    }
    //BFS 广度优先搜索
    int findCheapestPrice2(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        graph=vector<vector<vector<int>>>(n);
        for(auto flight:flights){
            graph[flight[0]].push_back(vector<int>{flight[1],flight[2]});
        }
        vector<int>ans(n,INF);
        queue<vector<int>>que;
        int res=-1;
        que.push(vector<int>{src,0});
        while(!que.empty()&&k+1>0){
            int size=que.size();
            for(int i=0;i<size;i++){
                auto node=que.front();
                que.pop();
              /*  if(node[0]==dst&&(res==-1||res>node[1])){
                    res=node[1];
                    continue;
                }*/
                for(auto neigh:graph[node[0]]){
                    int dis=node[1]+neigh[1];
                    if(dis<ans[neigh[0]]){
                        ans[neigh[0]]=dis;
                        que.push(vector<int>{neigh[0],dis});
                    }
                }
            }
            k--;
      }
        return ans[dst];
    }
};


#endif //LEETCODE_SOLUTION25_H
